/*
 * @lc app=leetcode.cn id=715 lang=cpp
 *
 * [715] Range 模块
 */
#include "include.h"
// @lc code=start
class RangeModule {
public:
    RangeModule() {
        root_ = new SegTreeNode(1, 1e9);
        leafHead_ = new LeafNode(root_);
        root_->leaf = leafHead_;
    }

    ~RangeModule(){
        clearTree(root_);
        clearList(leafHead_);
    }
    
    void addRange(int left, int right) {
        setRangeStatus(left, right, 1);
    }
    
    bool queryRange(int left, int right) {
        SegTreeNode* leftBelonging = findBelongingLeft(left, root_);
        SegTreeNode* rightBelonging = findBelongingRight(right, root_);

        LeafNode* leftLeaf = leftBelonging->leaf;
        LeafNode* rightLeaf = rightBelonging->leaf;

        LeafNode* temp = leftLeaf;

        while (temp != rightLeaf->next){
            if (temp->leafInfo->status != 1){
                return false;
            }
            temp = temp->next;
        }
        return true;
    }
    
    void removeRange(int left, int right) {
        setRangeStatus(left, right, 0);
    }
private:
    struct LeafNode;
    struct SegTreeNode
    {
        // [start, end)
        int start, end;
        // 0: free, 1: used / tracked, -1: not leaf (has left & right)
        int status;
        SegTreeNode *left, *right;
        
        LeafNode* leaf = nullptr;

        SegTreeNode() : start(0), end(0), status(0), left(nullptr), right(nullptr){}
        SegTreeNode(int from, int to) : start(from), end(to), status(0), left(nullptr), right(nullptr){}
        SegTreeNode(int from, int to, int tracked) : start(from), end(to), status(tracked), left(nullptr), right(nullptr){}
    };
    struct LeafNode
    {
        SegTreeNode* leafInfo;
        // LeafNode* prev;
        LeafNode* next;

        LeafNode(SegTreeNode* infoPtr) : leafInfo(infoPtr), next(nullptr) {}
    };
    
private:
    void setRangeStatus(int left, int right, int status){
        SegTreeNode* leftBelonging = findBelongingLeft(left, root_);
        SegTreeNode* rightBelonging = findBelongingRight(right, root_);

        if (leftBelonging == rightBelonging){

            SegTreeNode* root = leftBelonging;
            if (root->status == status){return;}

            int rootStatus = root->status;
            if (root->start == left and root->end == right){
                root->status = status;
            }else if(root->start == left) {
                root->status = -1;
                root->left = new SegTreeNode(root->start, right, status);
                root->right = new SegTreeNode(right, root->end, rootStatus);

                addNewLeaf(root);
            }else if(root->end == right) {
                root->status = -1;
                root->left = new SegTreeNode(root->start, left, rootStatus);
                root->right = new SegTreeNode(left, root->end, status);

                addNewLeaf(root);
            }else{
                // default right insert
                // todo : left , right ~ half root
                root->status = -1;
                root->left = new SegTreeNode(root->start, left, rootStatus);
                root->right = new SegTreeNode(left, root->end, -1);

                addNewLeaf(root);

                root = root->right;
                root->left = new SegTreeNode(root->start, right, status);
                root->right = new SegTreeNode(right, root->end, rootStatus);

                addNewLeaf(root);
            }

        }else{
            LeafNode* leftLeaf = leftBelonging->leaf;
            LeafNode* rightLeaf = rightBelonging->leaf;

            LeafNode* temp = leftLeaf->next;
            while(temp != rightLeaf){
                temp->leafInfo->status = status;
                temp = temp->next;
            }

            // split leftBelonging / rightBelonging
            if (left == leftBelonging->start){
                leftBelonging->status = status;
            }else{
                leftBelonging->left = new SegTreeNode(leftBelonging->start, left, leftBelonging->status);
                leftBelonging->right = new SegTreeNode(left, leftBelonging->end, status);
                leftBelonging->status = -1;
                addNewLeaf(leftBelonging);
            }

            if (right == rightBelonging->end){
                rightBelonging->status = status;
            }else{
                rightBelonging->left = new SegTreeNode(rightBelonging->start, right, status);
                rightBelonging->right = new SegTreeNode(right, rightBelonging->end, rightBelonging->status);
                rightBelonging->status = -1;
                addNewLeaf(rightBelonging);
            }
        }
    }

    void addNewLeaf(SegTreeNode* root){
        LeafNode* origin = root->leaf;
        LeafNode* temp = new LeafNode(root->right);
        temp->next = origin->next;
        origin->next = temp;
        origin->leafInfo = root->left;
        
        root->leaf = nullptr;
        root->left->leaf = origin;
        root->right->leaf = temp;
    }
private:
    SegTreeNode* root_;
    LeafNode* leafHead_;
private:
    void clearTree(SegTreeNode* root){
        // post order traverse
        if (root->left){clearTree(root->left);}
        if (root->right){clearTree(root->right);}

        // do
        delete root;
    }
    void clearList(LeafNode* leaf){
        if (!leaf) {return;}
        clearList(leaf->next);
        delete leaf;
    }

    SegTreeNode* findBelongingLeft(int x, SegTreeNode* root){
        if (root->status == -1){
            if (x < root->right->start){return findBelongingLeft(x, root->left);}
            else {return findBelongingLeft(x, root->right);}
        }else{
            return root;
        }
    }
    SegTreeNode* findBelongingRight(int x, SegTreeNode* root){
        if (root->status == -1){
            if (x <= root->right->start){return findBelongingRight(x, root->left);}
            else {return findBelongingRight(x, root->right);}
        }else{
            return root;
        }
    }
};

/**
 * Your RangeModule object will be instantiated and called as such:
 * RangeModule* obj = new RangeModule();
 * obj->addRange(left,right);
 * bool param_2 = obj->queryRange(left,right);
 * obj->removeRange(left,right);
 */
// @lc code=end

int main(){
    RangeModule test;
    test.addRange(10, 180);
    test.addRange(150, 200);
    test.addRange(250, 500);

    // 10 ----- 180 
    //       150 - 200 250 - 500
    //  50~100   180~~~~300
    //                               600 ~ 1000
    bool ck1 = test.queryRange(50, 100);
    bool ck2 = test.queryRange(180, 300);
    bool ck3 = test.queryRange(600, 1000);

    test.removeRange(50, 150);

    bool ck4 = test.queryRange(50, 100);

    printf("res %d %d %d %d\n", ck1,ck2,ck3,ck4);
}

// ["RangeModule","addRange","addRange","addRange","queryRange","queryRange","queryRange","removeRange","queryRange"]\n[[],[10,180],[150,200],[250,500],[50,100],[180,300],[600,1000],[50,150],[50,100]]
